// 2025/11/6
// 买卖股票的最佳时机2

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 前一天持有股票的最大值和前一天未持有股票的最大值
        int hold = -prices[0], sold = 0, n = prices.size(); 
        for(int i = 1; i < n; i++)
        {
            int cur_hold = max(hold, sold - prices[i]);
            int cur_sold = max(sold, hold + prices[i]);
            hold = cur_hold;
            sold = cur_sold;
        }
        return sold;
    }
};